1. Field of the Invention
This invention relates to method and apparatus for adding more than two multi-bit inputs.
2. Art Background
Digital integrated circuity, such as adder integrated circuits (ICs), that perform the binary addition of two input values are well known and widely used. Binary refers to the base-2 number system, in which values are expressed as combinations of two digits, 0 and 1. Binary digits are called bits. There are as many number based systems as there are numbers, but only a few number based systems are commonly used. Human beings generally represent numbers using the base-10 number system. Binary digital computers, on the other hand, represent information based on two states, logical ON and logical OFF. While many binary encoding schemes exist, it is common for binary digital computers to represent numbers internally using the base-2 number system and then convert numbers to base-10 when the numbers must be interpreted by humans.
The base of a number system is called its radix. Regardless of the radix used in a number system, the position of a digit with respect to a radix point (i.e. the place) is used to evaluate the number. The radix point is the period or other character that separates the integer portion of a number from the fractional portion. Depending upon the place of a digit in a number, each digit is multiplied by a power of the radix and the products are summed when the number is evaluated. The order of a place is the power to which a radix is raised when evaluating a digit located in that particular place.
In the base-10 system, a radix point is called a decimal point. The position of each base-10 digit with respect to the decimal point (i.e. the decimal place) provides the information necessary to evaluate a base-10 number. Thus the base-10 number 13.5 represents (1 * 10.sup.1)+(3 * 10.sup.0)+(5 * 10.sup.-1). Within a base-10 number, the decimal place in which a particular base-10 digit is located determines the order for the particular base-10 digit. In the base-10 number 13.5, the base-10 digit 3 in the one's place would have an order of zero because 3 is multiplied by 10 to the zeroeth power when evaluating the number. The same number represented by the base-10 number 13.5 would be depicted by 1101.1 as a binary number. That is because the binary number 1101.1 represents (1 * 2.sup.3)+(1 * 2.sup.2)+(0 * 2.sup.1)+ (1 * 2.sup.0)+(1 * 2.sup.-1) (which is the same as the sum of the base-10 numbers 8+4+0+1+0.5).
Various schemes are commonly used to represent binary numbers. Offset binary representation is commonly used in analog/digital (A/D) and digital/analogue (D/A) conversions. In offset binary representation, half the largest possible number is substrated to get the value represented. This has the advantage that the number sequence from the most negative to the most positive is a simple binary progression. The most significant bit (MSB) carries the sign information, and zero appears only once. The method most widely used for integer computation is called two's complement ("2's complement"). In this system, positive numbers are represented as simple unsigned binary numbers. The system is contrived such that a negative number is then represented as the binary number that would be added to a positive number of the same magnitude to yield zero. A negative number is formed by complementing each of the bits of the positive number and then adding one. A one in the MSB indicates a negative number and there is only zero in this system. Arithmetic is simple in 2's complement because the sign information is carried in the MSB. To add two numbers, one simply adds them bitwise starting with the least significant bit (LSB). A carry from a lower bit is added into the next higher bit. A carry from the sign bit, i.e., the MSB, is simply ignored.
It is common in the art to perform addition using a combinational circuit. A half-adder is a combinational circuit that performs the arithmetic addition of two binary digits. The input variables of a half-adder are called augend and addend bits (X and Y, respectively, in this example). The output variables are called the sum and carry (S and C, in this example). The Table below depicts the truth table for a half-adder.
TABLE 1 ______________________________________ INPUTS OUTPUTS X Y C S ______________________________________ 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 ______________________________________
A truth table depicts the output variable values for every possible combination of input variable values. From the truth table it may be seen that when the input variables X and Y both have the value of zero, the output variables (sum and carry) will also have the value of zero. Similarly, when X and Y are both one, the sum will be zero and the carry will be one. Finally, when, either X is zero and Y is one, or when Y is zero and X is one, the sum will be one and the carry will be zero. Stated another way, the C output is zero unless both inputs are one and the S output is one unless both inputs are the same. Thus, Boolean functions may be obtained directly from the truth table: C=X AND Y;S=X XOR Y. Logic circuitry for this relationship consists of an exclusive-OR gate with X and Y as inputs and S as an output and an AND gate with X and Y as inputs and C as an output.
It is possible to design combinational circuitry of greater complexity. However, certain applications arise so frequently that off-the-shelf integrated circuits are available which permit a designer to forego the difficulty of designing specialized combinatorial circuity for a particular need. One such commonly required application is a four-bit adder.
A four-bit adder adds a first four bit number to a second four bit number generating a four bit sum plus a carry bit. It is common to "expand" adders to add larger numbers. For example, two eight-bit numbers can be added using two four-bit adders by summing the four LSBs of the addends in one four-bit adder (the LSB adder) and the four MSBs of the addends plus the carry bit from the LSB addition in the other four-bit adder (the MSB adder). The carry bit from the MSB adder provides the ninth bit for the resulting sum which is formed by combining the four LSBs output from the LSB adder with the four MSBs output from the MSB adder.
However, conventional off-the-shelf adder ICs are only capable of adding two numbers at a time. Furthermore, they are too slow to accommodate large numbers (greater than 16 bits) in very fast applications. In an application requiring fast, complex addition such as matrix manipulation and digital signal processing (DSP) applications, it may be necessary to add more than two very large numbers at speeds above 20 MHz. It may also be necessary to clip negative sums to zero and positive sums above a threshold to that threshold. Using typical four-bit "fast" adder ICs and designing for worst case conditions would require four pipeline stages and roughly 32 16-bit equivalent ICs for this operation. The method and apparatus of the present invention can accomplish this task in three pipeline stages and require only 16 16-bit equivalent ICs.